package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/binary-tree-inorder-traversal/'>二叉树的中序遍历(Binary Tree Inorder Traversal)</a>
 * <p>给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,2,3]
 *      输出：[1,3,2]
 *
 * 示例 2：
 *      输入：root = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：root = [1]
 *      输出：[1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中节点数目在范围 [0, 100] 内</li>
 *         <li>-100 <= Node.val <= 100</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0094BinaryTreeInorderTraversal_S 二叉树的中序遍历
 * @see LC0144BinaryTreePreorderTraversal_S 二叉树的前序遍历
 * @see LC0145BinaryTreePostorderTraversal_S 二叉树的后序遍历
 * @since 2023/11/1 17:37
 */
public class LC0094BinaryTreeInorderTraversal_S {
    static class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            //return inorderTraversalByRecursion(root);
            return inorderTraversalByIterator(root);
        }

        private List<Integer> inorderTraversalByIterator(TreeNode root) {
            List<Integer> resultList = new ArrayList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode currNode = root;
            while (currNode != null || !stack.isEmpty()) {
                while (currNode != null) {
                    stack.addFirst(currNode);
                    currNode = currNode.left;
                }
                currNode = stack.removeFirst();
                resultList.add(currNode.val);
                currNode = currNode.right;
            }
            return resultList;
        }

        private List<Integer> inorderTraversalByRecursion(TreeNode root) {
            List<Integer> resultList = new ArrayList<>();
            inorderTraversalByRecursion(root, resultList);
            return resultList;
        }

        private void inorderTraversalByRecursion(TreeNode root, List<Integer> resultList) {
            if (root == null) {
                return;
            }
            inorderTraversalByRecursion(root.left, resultList);
            resultList.add(root.val);
            inorderTraversalByRecursion(root.right, resultList);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListInteger(solution.inorderTraversal(null));
        //Printer.printListInteger(solution.inorderTraversal2(null));

        TreeNode node1 = new TreeNode(1);
        Printer.printListInteger(solution.inorderTraversal(node1));
        //Printer.printListInteger(solution.inorderTraversal2(node1));

        TreeNode node2 = new TreeNode(1);
        node2.right = new TreeNode(2);
        node2.right.left = new TreeNode(3);
        Printer.printListInteger(solution.inorderTraversal(node2));
        //Printer.printListInteger(solution.inorderTraversal2(node2));
    }
}
